/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-14
 * Time: 9:15
 */
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Solution1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        //存放体积
        int[] v = new int[n+1];
        //存放价值
        int[] w = new int[n+1];

        for(int i = 1; i <= n; i++) {
            //体积
            v[i] = in.nextInt();
            //价值
            w[i] = in.nextInt();
        }

        //解决第一问
        int[][] dp1 = new int[n+1][V+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp1[i][j] = dp1[i-1][j];
                if(j-v[i] >= 0) {
                    dp1[i][j] = Math.max(dp1[i-1][j-v[i]]+w[i],dp1[i][j]);
                }
            }
        }
        System.out.println(dp1[n][V]);

        //解决第二问
        int[][] dp2 = new int[n+1][V+1];

        for(int j = 1; j <= V; j++) {
            dp2[0][j] = -1;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp2[i][j] = dp2[i-1][j];
                if(j-v[i] >= 0 && dp2[i-1][j-v[i]] != -1) {
                    dp2[i][j] = Math.max(dp2[i-1][j-v[i]]+w[i],dp2[i][j]);
                }
            }
        }

        System.out.println( dp2[n][V] == -1 ? 0 : dp2[n][V]);
    }
}


//优化后
//改动代码 遍历顺序 去掉i
/*
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        //存放体积
        int[] v = new int[n+1];
        //存放价值
        int[] w = new int[n+1];

        for(int i = 1; i <= n; i++) {
            //体积
            v[i] = in.nextInt();
            //价值
            w[i] = in.nextInt();
        }

        //解决第一问
        int[] dp1 = new int[V+1];
        for(int i = 1; i <= n; i++) {
            for(int j = V; j >= v[i]; j--) {
                dp1[j] = Math.max(dp1[j-v[i]]+w[i],dp1[j]);
            }
        }

        System.out.println(dp1[V]);

        //解决第二问
        int[] dp2 = new int[V+1];

        for(int j = 1; j <= V; j++) {
            dp2[j] = -1;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = V; j >= v[i]; j--) {
                if(dp2[j-v[i]] != -1) {
                    dp2[j] = Math.max(dp2[j-v[i]]+w[i],dp2[j]);
                }
            }
        }

        System.out.println( dp2[V] == -1 ? 0 : dp2[V]);
    }
}*/